DROPS

Document

Brief Announcement

DOI: 10.4230/LIPIcs.DISC.2021.47

Brief Annoucement: On Extending Brandt’s Speedup Theorem from LOCAL to Round-Based Full-Information Models

Authors: Paul Bastide and Pierre Fraigniaud

Published in: LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021)

Abstract

Given any task Π, Brandt’s speedup theorem (PODC 2019) provides a mechanical way to design another task Π' on the same input-set as Π such that, for any t ≥ 1, Π is solvable in t rounds in the LOCAL model if and only if Π' is solvable in t-1 rounds in the LOCAL model. We dissect the construction in Brandt’s speedup theorem for expressing it in the broader framework of all round-based models supporting full information protocols, which includes models as different as asynchronous wait-free shared-memory computing with iterated immediate snapshots, and synchronous failure-free network computing.

Cite as

Paul Bastide and Pierre Fraigniaud. Brief Annoucement: On Extending Brandt’s Speedup Theorem from LOCAL to Round-Based Full-Information Models. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 47:1-47:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bastide_et_al:LIPIcs.DISC.2021.47,
  author =	{Bastide, Paul and Fraigniaud, Pierre},
  title =	{{Brief Annoucement: On Extending Brandt’s Speedup Theorem from LOCAL to Round-Based Full-Information Models}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{47:1--47:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-210-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{209},
  editor =	{Gilbert, Seth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.47},
  URN =		{urn:nbn:de:0030-drops-148492},
  doi =		{10.4230/LIPIcs.DISC.2021.47},
  annote =	{Keywords: Local Checkability, Distributed Complexity and Computability}
}

Search Results

Documents authored by Bastide, Paul

Brief Annoucement: On Extending Brandt’s Speedup Theorem from LOCAL to Round-Based Full-Information Models

Abstract

Cite as

Thanks for your feedback!

Could not send message